﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StrategyAndSort
{
    /// <summary>
    /// 希尔排序
    /// </summary>
    class ShellSort : ISortStrategy
    {
        public void Sort<T>(IList<T> array,int keyNum =0) where T : IComparable
        {
            for(int d = array.Count / 2; d >0; d = d / 2)
            {
                //找到第i个待插入的元素
                for (int i = d; i < array.Count; i++)
                {
                    int j;
                    if (array[i].CompareTo(array[i - d])<0){
                        T temp = array[i];
                        //在有序序列里腾出一个空位
                        for (j = i - d; j >= 0 && temp.CompareTo(array[j]) < 0; j -= d)
                        {
                            array[j + d] = array[j];
                        }
                        //for( j = i - d; j >= 0; j-=d)
                        //{
                        //    if(temp.CompareTo(array[j])<0)
                        //        array[j + d] = array[j];
                        //    else 
                        //        break;
                        //}
                        array[j + d] = temp;
                    }
                }
            }
        }


    }
}
